#include <iostream>
#include <vector>

using namespace std;

void shellsort(vector<int>& nums){
    int n = nums.size();
    for(int gap = n / 2; gap > 0; gap /= 2){
        for(int i = gap; i < n; ++i){
            int temp = nums[i];
            int j;
            for(j = i; j >= gap && nums[j - gap] > temp; j -= gap)
                nums[j] = nums[j - gap];
            nums[j] = temp; 
        }
    }
}


int main(){
    vector<int> ans = {4,5,1,2,3};
    shellsort(ans);
    for(auto& x : ans)
        cout << x << " ";
}